// write your code here cpp
#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int f_arr[10000] = {0,1,2};
    for(int i = 3;i < 10001;i++)
    {
        f_arr[i] = f_arr[i-1] + f_arr[i-2];
        f_arr[i] %= 10000;
    }
    
    int n;
    
    while(cin >> n)
    {
        for(int i = 0;i < n;i++)
        {
            int num;
            cin >> num;
            f_arr[num];
            
            printf("%04d",f_arr[num]);
        }
        printf("\n");
    }
    return 0;
}
